Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11590 - Prefix lookup / 11590.8.cpp
blob7a5b74c140f6e0acb2c9ceab508817fe4c35c36b
1 //Accepted
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <sstream>
7 #include <fstream>
8 #include <cassert>
9 #include <climits>
10 #include <cstdlib>
11 #include <cstring>
12 #include <string>
13 #include <cstdio>
14 #include <vector>
15 #include <cmath>
16 #include <queue>
17 #include <deque>
18 #include <stack>
19 #include <list>
20 #include <map>
21 #include <set>
23 #define D(x) cout << #x " = " << (x) << endl
25 typedef unsigned long long Int;
26 const int BUFSIZE = 256;
27 char buf[BUFSIZE];
29 int M;
30 map<string, Int> ans;
32 struct node{
33 node * left, * right;
34 bool end; //is this node a complete prefix?
35 node(bool e) : end(e) {
36 left = right = NULL;
40 //not used, because I love to waste memory (makes me feel sexy)
41 void clean(node * n){
42 if (n == NULL) return;
43 clean(n->left); clean(n->right);
44 delete n;
47 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
48 Int left = 0, right = 0, ret = 0;
49 if (n->left != NULL){
50 left = f(s + "0", n->left);
52 if (n->right != NULL){
53 right = f(s + "1", n->right);
55 ret += left + right;
57 if (n->end){
58 Int howmany;
59 if (M - s.size() < 64){ //we are safe from overflow
60 Int x = ((1ULL) << (M - s.size())); //2^(m - |s|)
61 howmany = x - left - right;
62 }else{ //2^64 overflows!
63 Int x = 0;
64 x = ~x; // (x = ~0ULL) <-> (x = 2^64 - 1)
65 howmany = x - left - right + 1;
67 ret += howmany;
68 ans[s] = howmany;
70 return ret;
73 int main(){
74 int n;
75 while (scanf("%d%d\n", &n, &M)==2 && !(n == 0 && M == 0)){
76 ans.clear();
77 node * root = new node(true);
78 while (n--){
79 scanf("%s", buf);
80 node * cur = root;
81 for (int i=0; ; ++i){
82 if (buf[i] == '*'){
83 cur->end = true;
84 break;
86 if (buf[i] == '0'){
87 if (cur->left == NULL) cur->left = new node(false);
88 cur = cur->left;
89 }else if (buf[i] == '1'){
90 if (cur->right == NULL) cur->right = new node(false);
91 cur = cur->right;
96 f("", root);
98 int K;
99 scanf("%d\n", &K);
100 while (K--){
101 scanf("%s", buf);
102 buf[strlen(buf)-1] = 0; //delete *
103 Int t = ans[string(buf)];
104 printf("%llu\n", t);
106 puts("");
108 return 0;